﻿using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;

namespace TaskFramework
{
    public class TaskQueue : ITaskQueue
    {
        private readonly ITaskTracker _taskTracker;

        private TaskInfo[] _items;
        private readonly List<int> _rootTaskIds = new List<int>();

        private const int DEFAULT_CAPACITY = 16;
        private readonly int _initialCapacity;
        private int _capacity;
        private int _itemCount;

        public TaskQueue(ITaskTracker taskTracker)
        {
            _taskTracker = taskTracker;
            _taskTracker.RootTaskDead += _taskTracker_RootTaskRemoved;

            _itemCount = 0;
            _initialCapacity = DEFAULT_CAPACITY;
            SetCapacity(_initialCapacity);
        }

        void _taskTracker_RootTaskRemoved(int rootTaskId)
        {
            _rootTaskIds.Remove(rootTaskId);
        }

        public void Enqueue(TaskInfo info)
        {
            int rootTaskId;
            if (info.IsRootTask)
            {
                rootTaskId = info.Task.TaskId;
                _rootTaskIds.Add(rootTaskId);
            }
            else
            {
                rootTaskId = _taskTracker.ResolveRootTaskId(info.Task.TaskId);
            }

            Debug.Assert(_rootTaskIds.Contains(rootTaskId));

            if (_itemCount == _capacity) // need to increase capacity, grow by 100 percent
            {
                SetCapacity(_capacity * 2);
            }

            int insertIndex;

            if (_itemCount > 0)
            {
                insertIndex = _itemCount;

                while (insertIndex > 0)
                {
                    TaskInfo next = _items[insertIndex - 1];
                    int nextRootTaskId = _taskTracker.ResolveRootTaskId(next.Task.TaskId);

                    if (_rootTaskIds.IndexOf(nextRootTaskId) <= _rootTaskIds.IndexOf(rootTaskId))
                    {
                        break;
                    }

                    insertIndex--;
                }
            }
            else
            {
                insertIndex = 0;
            }

            // create a gap at the insert index
            for (int i = _itemCount; i > insertIndex; i--)
            {
                _items[i] = _items[i - 1];
            }

            _itemCount++;
            _items[insertIndex] = info;
        }

        public TaskInfo Dequeue()
        {
            if (_itemCount == 0)
            {
                throw new InvalidOperationException("The queue is empty.");
            }

            TaskInfo dequeued = _items[0];
            _itemCount--;

            // move remaining items to fill gap at head of queue
            int i = 0;
            while (i < _itemCount)
            {
                _items[i] = _items[i + 1];
                i++;
            }
            _items[i] = null;

            return dequeued;
        }

        public TaskInfo Peek()
        {
            if (_itemCount > 0)
            {
                return _items[0];
            }

            throw new InvalidOperationException("The queue is empty.");
        }

        public int Count
        {
            get { return _itemCount; }
        }

        public void Clear()
        {
            // null each item in the queue
            for (int i = 0; i < _itemCount; i++)
            {
                _items[i] = null;
            }

            _rootTaskIds.Clear();
            SetCapacity(_initialCapacity);
        }

        private void SetCapacity(int newCapacity)
        {
            if (newCapacity < _itemCount)
            {
                throw new ArgumentOutOfRangeException("newCapacity", "New capacity is less than Count.");
            }

            if (_items == null)
            {
                _items = new TaskInfo[newCapacity];
            }
            else
            {
                Array.Resize(ref _items, newCapacity);
            }

            _capacity = newCapacity;
        }
    }
}